package sol.leetcode;

/**
 * Best Time to Buy and Sell Stock III
 */
public class Issue123 {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;

        int n = prices.length;
        int[] preProfit = new int[n];
        int[] postProfit = new int[n];

        int bought = prices[0];
        for (int i = 1; i < n; i++) {
            bought = Math.min(bought, prices[i]);
            preProfit[i] = Math.max(preProfit[i - 1], prices[i] - bought);
        }

        int sell = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            sell = Math.max(sell, prices[i]);
            postProfit[i] = Math.max(postProfit[i + 1], sell - prices[i]);
        }

        int maxProfit = 0;
        for (int i = 0; i < n; i++) {
            maxProfit = Math.max(maxProfit, preProfit[i] + postProfit[i]);
        }

        return maxProfit;
    }


    public static void main(String[] args) {
        int[] prices = {2, 3, 1, 5, 6};
        Issue123 sol = new Issue123();
        System.out.println(sol.maxProfit(prices));

    }
}
